﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;


namespace Algoritmia.DataStructures.PriorityMaps
{
    public class HeapMap<TKey,TValue> : IPriorityMap<TKey,TValue>
    {
        private static readonly IEnumerable<KeyValuePair<TKey,TValue>> DefaultElement = new[] { default(KeyValuePair<TKey,TValue>) };
        private readonly Func<KeyValuePair<TKey, TValue>, KeyValuePair<TKey, TValue>
            , bool> _firstHasHigherPriority;
        private readonly Func<IEnumerable<KeyValuePair<TKey,TValue>>,IMap<TKey, int>> _createMap;
        private readonly Func<IMap<TKey, int>, TKey , IMap<TKey,int>> _redimensionMap;
        private readonly IMap<TKey, int> _index;

        private KeyValuePair<TKey, TValue>[] _heap;
        private int _capacity;
        private int _count;

        private readonly KeysView<TKey, TValue> _keysView;
        private readonly ItemsView<TKey, TValue> _itemsView;
        private readonly ValuesView<TKey, TValue> _valuesView;

        public HeapMap(IEnumerable<KeyValuePair<TKey, TValue>> data = null, 
            int capacity = 0, 
            Func<KeyValuePair<TKey, TValue>, KeyValuePair<TKey, TValue>, bool> firstHasHigherPriority = null,
            Comparison<KeyValuePair<TKey, TValue>> comparison = null,
            Func<IEnumerable<KeyValuePair<TKey,TValue>>,IMap<TKey,int>> createMap=null,
            Func<IMap<TKey,int>,TKey,IMap<TKey,int>> redimensionMap=null
            )
        {
            _firstHasHigherPriority = GetPriorityFunction(comparison, firstHasHigherPriority);
            _createMap = createMap ?? (items => AlgoritmiaFactory.Maps<TKey, int>.Default);
            _redimensionMap = redimensionMap ?? ((map, key) => map );

            _heap = DefaultElement.Concat(data ?? Enumerable.Empty<KeyValuePair<TKey,TValue>>()).ToArray();
            _index = _createMap(data);

            for (var i = 1; i < _heap.Length; i++)
            {
                _index[_heap[i].Key] = i ;
            }

            _count = _heap.Length-1;
            _capacity = Math.Max(_count, capacity <= 0 ? 1 : capacity);

            if (_capacity > _count)
            {
                Array.Resize(ref _heap, _capacity + 1);
            }

            BuildHeap();

            _keysView = new KeysView<TKey, TValue>(this);
            _itemsView = new ItemsView<TKey, TValue>(this);
            _valuesView = new ValuesView<TKey, TValue>(this);
        }

        private void BuildHeap()
        {
            for (var i = _count / 2; i > 0; i--)
            {
                Heapify(i);
            }
        }

        protected void Swap(int i, int j)
        {
            var aux = _heap[i];
            _heap[i] = _heap[j];
            _heap[j] = aux;
        }

        private void Heapify(int index)
        {
            var best = index;
            while (true)
            {
                var left = 2 * index;
                var right = 2 * index + 1;
                if (left <= _count && _firstHasHigherPriority(_heap[left], _heap[index]))
                {
                    best = left;
                }
                if (right <= _count && _firstHasHigherPriority(_heap[right], _heap[best]))
                {
                    best = right;
                }
                if (best == index) break;

                //Updating index map
                _index[_heap[index].Key] = best;
                _index[_heap[best].Key] = index;

                Swap(index, best);
                index = best;
            }
        }

        private void BubbleUp(int index)
        {
            int parent = index / 2;
            while (index > 1 && _firstHasHigherPriority(_heap[index], _heap[parent]))
            {
                //Updating index map
                _index[_heap[index].Key] = parent;
                _index[_heap[parent].Key] = index;
                Swap(parent, index);
                index = parent;
                parent /= 2;
            }
        }

        private void DoubleHeapCapacity()
        {
            _capacity *= 2;
            Array.Resize(ref _heap,_capacity + 1);
        }

        private static Func<KeyValuePair<TKey, TValue>, KeyValuePair<TKey, TValue>, bool> GetPriorityFunction(Comparison<KeyValuePair<TKey, TValue>> comparison, 
            Func<KeyValuePair<TKey, TValue>, KeyValuePair<TKey, TValue>, bool> firstHasHigherPriority)
        {
            if (comparison != null && firstHasHigherPriority != null)
            {
                throw new ArgumentException("You can't define firstHasHigherPriority and comparer simultaneously");
            }
            if (comparison != null)
            {
                return (first, second) => comparison(first, second) < 0;
            }
            if (firstHasHigherPriority == null)
            {
                if (typeof(TValue).GetInterfaces().Contains(typeof(IComparable<TValue>)))
                {
                    if (typeof(TKey).GetInterfaces().Contains(typeof(IComparable<TKey>)))
                    {
                        return (first, second) => ( Comparer<TValue>.Default.Compare(first.Value, second.Value) == 0 ?
                              Comparer<TKey>.Default.Compare(first.Key, second.Key) > 0 : Comparer<TValue>.Default.Compare(first.Value, second.Value) > 0);
                    }
                    return (first, second) => (Comparer<TValue>.Default.Compare(first.Value, second.Value) > 0);
                }
                throw new ArgumentException("No comparison criterium on non comparable data");
            }
            return firstHasHigherPriority;
        }

        #region IPriorityMap<TKey,TValue> Members

        public KeyValuePair<TKey, TValue> GetOptimal()
        {
            if (_count == 0)
                throw new InvalidOperationException("Can't extract anything from an empty heap map.");
            return _heap[1];
        }

        public KeyValuePair<TKey, TValue> ExtractOptimal()
        {
            if (_count == 0)
                throw new InvalidOperationException("Can't extract anything from an empty heap.");
            var kv = _heap[1];
            _heap[1] = _heap[_count];
            _index.Remove(kv.Key);
            _count--;
            if (_count > 1) Heapify(1);
            return kv;
        }

        #endregion

        #region IMap<TKey,TValue> Members

        public TValue this[TKey key]
        {
            get { return _heap[_index[key]].Value; }
            set
            {
                int i;
                var kv = new KeyValuePair<TKey, TValue>(key, value);
                if ( _index.Contains(key))
                {
                    i = _index[key];
                    if ( !_firstHasHigherPriority(kv,_heap[i]) )
                    {
                        _heap[i] =  kv;
                        Heapify(i);
                        return;
                    }
                }
                else
                {
                   _redimensionMap(_index, key);
                   _index[key] = i =  ++_count;
                    if (_count > _capacity)
                    {
                        DoubleHeapCapacity();
                    }
                }
                _heap[i] = kv;
                BubbleUp(i);
            }
        }

        public void Add(TKey key, TValue value)
        {
            this[key] = value;
        }

        public bool Contains(TKey key)
        {
            return _index.Contains(key);
        }

        public TValue Get(TKey key, TValue defaultValue)
        {
            if (!_index.Contains(key))
                return defaultValue;
            return _heap[_index[key]].Value;
        }

        public ICollectionView<TKey> Keys()
        {
            return _keysView;
        }

        public ICollectionView<KeyValuePair<TKey, TValue>> Items()
        {
            return _itemsView;
        }

        public bool Remove(TKey key)
        {
            if (!_index.Contains(key))
            {
                return false;
            }
            int i = _index[key];
            _index.Remove(key);
            _index[_heap[_count].Key] = i;
            Swap(i,_count);
            _count--;
            Heapify(i);
            BubbleUp(i);
            return true;
        }

        public TValue SetDefault(TKey key, TValue defaultValue)
        {
            if (!_index.Contains(key))
            {
                this[key] = defaultValue;
                return defaultValue;
            }
            return _heap[_index[key]].Value;
        }

        public ICollectionView<TValue> Values()
        {
            return _valuesView;
        }

        #endregion

        #region IEnumerable<KeyValuePair<TKey,TValue>> Members

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            for(var i = 1;i <= _count;i++)
            {
                yield return _heap[i];
            }
        }

        #endregion

        #region IEnumerable Members

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        #endregion

        #region ICountable Members

        public int Count
        {
            get { return _count; }
        }

        #endregion

        public override string ToString()
        {
            return String.Format("{0} <{1},{2}> [{3}]", GetType().Name, typeof (TKey).Name, typeof (TValue).Name,
                                 string.Join(",", this));
        }
    }
}
